/**
 * @file filename.cpp
 * @brief nullptr关键字用于标识空指针，与NULL不同，NULL为0
 * @author Monomania (1301519350@qq.com)
 * @version 0.1
 * @date 2021-09-23
 */
#include<iostream>
#include <vector> 
#include <string>
#include <list>
#include <map>
#include <algorithm> // std::minmax_element
#include <boost/algorithm/string.hpp>
#include <functional>
#include <iterator>
// #define NDEBUG
#include <assert.h>
using namespace std;

#define OK 1
#define ERROR 0
#define TRUE true
#define FALSE false
// 定义一个不可能的数
#define INF   -99999  
#define MAXSIZE 20 /* 存储空间初始分配量 */

typedef int Status; 
typedef int SElemType; /* SElemType类型根据实际情况而定，这里假设为int */


class Solution {
public:
    string addBinary(string a, string b) {
        string ans;
        int carry=0;  // 进位
        int i;
        reverse(a.begin(),a.end());
        reverse(b.begin(),b.end());
        for (i=0; i<a.size() || i<b.size(); i++)
        {
            int tmp = 0;
            if (i < a.size() && i < b.size()){
                tmp = transData(a[i]) + transData(b[i]) + carry;
            }
            else if (i < a.size() && i >= b.size())
            {
                tmp = transData(a[i]) + carry;
            }
            else{
                tmp = transData(b[i]) + carry;
            }

            if (tmp == 0){
                ans.push_back('0');
                carry = 0;
            }
            else if (tmp == 1){
                ans.push_back('1');
                carry = 0;
            }
            else if (tmp == 2){
                ans.push_back('0');
                carry = 1;
            }
            else if (tmp == 3){
                ans.push_back('1');
                carry = 1;
            }
            cout << i << ": " << carry << " - "<< ans << endl;
        }
        if (carry != 0)
        {
            ans.push_back('1');
        }
        // cout << ans << endl;
        reverse(ans.begin(),ans.end());
        return ans;
    }
    
    int transData(char ch){
        return (ch - '0');
    }
};


int main(int argc, const char** argv) {
    Solution solu = Solution();
    string a = "11", b = "1";
    // string a = "1010", b = "1011";

    cout << solu.addBinary(a, b) << endl;

    return 0;
}